#include <iostream>
using namespace std;
template <typename T>
class Node {
public:
	template <typename T>
	friend class AVL;
	Node(T value);
	Node(Node<T>& node);
	Node(T value,  int height, Node<T>* left, Node<T>* right);
	int getHeight();
	int getValue();
	void setLeft(Node<T>* left);
	void setRight(Node<T>* right);
	~Node();
private:
	T value;
	int height;
	Node<T>* leftChild;
	Node<T>* rightChild;
};
template <typename T>
Node<T>::Node(T value) {
	height = 0;
	this->value = value;
	leftChild = nullptr;
	rightChild = nullptr;
}
template <typename T>
Node<T>::Node(Node<T>& node) {
	this->height = node.height;
	this->value = node.value;
}
template <typename T>
Node<T>::~Node() {

}
template <typename T>
Node<T>::Node(T value,int height ,Node<T>* left, Node<T>* right) {
	this->height = height;
	this->value = value;
	leftChild = left;
	rightChild = right;
}
template <typename T>
void Node<T>::setLeft(Node<T>* left) {
	leftChild = left;
}
template <typename T>
void Node<T>::setRight(Node<T>* right) {
	rightChild = right;
}
template <typename T>
int Node<T>::getHeight() {
	if (this == nullptr)
		return -1;
	else
		return this->height;
}
template <typename T>
int Node<T>::getValue() {
	if (this == nullptr)
		return 0;
	else
		return this->value;
}

template <typename T>
class AVL {
public:
	AVL();
	~AVL();
	bool isEmpty();
	Node<T>* getRoot() { return _root; }
	int getSize();
	int getHeight(Node<T>* root);
	bool isBalanced();
	bool isBalanced(Node<T>* root);
	int getBalanceFactor(Node<T>* root);
	Node<T>* rightRotate(Node<T>* root);
	Node<T>* leftRotate(Node<T>* root);
	void add(T value);
	Node<T>* add(Node<T>* root, T value);
	T erase(T value);
	Node<T>* erase(Node<T>* root, T value);
	Node<T>* minofRight(Node<T>* root);
	void traverseinOrder(Node<T>* root);
	T valueofNearestLeaf();
	Node<T>* valueofNearestLeaf(Node<T>* root);
private:
	Node<T>* _root;
	int size;
};
template <typename T>
AVL<T>::AVL() {
	_root = nullptr;
	size = 0;
}
template <typename T>
AVL<T>::~AVL() {

}
template <typename T>
int AVL<T>::getHeight(Node<T>* root) {
	if (root == nullptr) {
		return -1;
	}
	return root->getHeight();
}
template <typename T>
int AVL<T>::getSize() {
	return this->size;
}
template <typename T>
bool AVL<T>::isEmpty() {
	return size == 0;
}
template <typename T>
int AVL<T>::getBalanceFactor(Node<T>* root) {
	if (root == nullptr)
		return 0;
	//return root->leftChild->getHeight() - root->rightChild->getHeight();
	return this->getHeight(root->leftChild) - this->getHeight(root->rightChild);
}
template <typename T>
bool AVL<T>::isBalanced(Node<T>* root) {
	if (root == nullptr)
		return true;
	if (this->getBalanceFactor(root)>1|| this->getBalanceFactor(root) < -1) 
		return false;
	return isBalanced(root->leftChild) && isBalanced(root->rightChild);
}
template <typename T>
bool AVL<T>::isBalanced() {
	return isBalanced(_root);
}
template <typename T>
Node<T>* AVL<T>::rightRotate(Node<T>* root) {
	Node<T>* x = root->leftChild;
	root->leftChild = x->rightChild;
	x->rightChild = root;
	root->height = max(root->leftChild->getHeight(), root->rightChild->getHeight()) + 1;
	x->height = max(x->leftChild->getHeight(), x->rightChild->getHeight()) + 1;
	/*Node<T>* x = root->leftChild;
	Node<T>* temp = x->rightChild;
	x->rightChild = root->rightChild;
	root->leftChild = x->leftChild;
	root->rightChild = x;
	x->leftChild = temp;
	Node<T> temp2(*root);
	root->value = x->value;
	x->value = temp2.value;
	x->height = max(x->leftChild->getHeight(), root->getHeight()) + 1;
	root->height = max(root->leftChild->getHeight(), root->rightChild->getHeight()) + 1*/;
	return x;
}
template <typename T>
Node<T>* AVL<T>::leftRotate(Node<T>* root) {
	Node<T>* x = root->rightChild;
	root->rightChild = x->leftChild;
	x->leftChild = root;
	root->height = max(root->leftChild->getHeight(), root->rightChild->getHeight()) + 1;
	x->height = max(x->leftChild->getHeight(), x->rightChild->getHeight()) + 1;
/*	Node<T>* x = root->rightChild;
	Node<T>* temp = x->leftChild;
	x->leftChild = root->leftChild;
	root->rightChild = x->rightChild;
	root->leftChild = x;
	x->rightChild = temp;
	Node<T> temp2(*root);
	root->value = x->value;
	x->value = temp2.value;
	x->height = max(x->leftChild->getHeight(), x->rightChild->getHeight()) + 1;
	root->height = max(root->leftChild->getHeight(), root->rightChild->getHeight()) + 1;*/
	return x;
}
template <typename T>
void AVL<T>::add(T value) {
		_root = add(_root,value);
}
template <typename T>
Node<T>* AVL<T>::add(Node<T>* root, T value) {
	if (root == nullptr) {
		size++;
		root = new Node<T>(value);
		return root;
	}
	if (value < root->getValue())
		root->leftChild = add(root->leftChild, value);
	else
		root->rightChild = add(root->rightChild, value);
	root->height = max(root->leftChild->getHeight(), root->rightChild->getHeight()) + 1;
	int balanceFactor = this->getBalanceFactor(root);
	if (balanceFactor > 1 && getBalanceFactor(root->leftChild) > 0)
		return rightRotate(root);
	if (balanceFactor < -1 && getBalanceFactor(root->rightChild) < 0)
		return leftRotate(root);
	if (balanceFactor > 1 && getBalanceFactor(root->leftChild) < 0) {
		root->leftChild = leftRotate(root->leftChild);
		return rightRotate(root);
	}
	if (balanceFactor < -1 && getBalanceFactor(root->rightChild) > 0) {
		root->rightChild = rightRotate(root->rightChild);
		return leftRotate(root);
	}
	return root;
}
template <typename T>
void AVL<T>::traverseinOrder(Node<T>* root){
	if (root == nullptr)
		return;
	traverseinOrder(root->leftChild);
	cout << root->getValue() << " ";
	traverseinOrder(root->rightChild);
}
template <typename T>
T AVL<T>::erase(T value) {
	_root = erase(_root, value);
	return value;
}
template <typename T>
Node<T>* AVL<T>::minofRight(Node<T>* root) {
	if (root->leftChild == nullptr)
		return root;
	minofRight(root->leftChild);
}
template <typename T>
Node<T>* AVL<T>::erase(Node<T>* root,T value) {
	if (root == nullptr)
		return nullptr;
	Node<T>* currentNode = nullptr;
	if (value < root->getValue()) {
		root->leftChild = erase(root->leftChild, value);
		currentNode = root;
	}
	else if (value > root->getValue()) {
		root->rightChild = erase(root->rightChild, value);
		currentNode = root;
	}
	else {
		if (root->leftChild == nullptr) {
			Node<T>* right = root->rightChild;
			root->rightChild = nullptr;
			size--;
			currentNode = right;
		}
		else if(root->rightChild == nullptr){
			Node<T>* left = root->leftChild;
			root->leftChild = nullptr;
			size--;
			currentNode = left;
		}
		else {
			Node<T>* min = minofRight(root->rightChild);
			min->rightChild = erase(root->rightChild, min->value);
			min->leftChild = root->leftChild;
			root->leftChild = root->rightChild = nullptr;
			currentNode = min;
		}
	}
	if (currentNode == nullptr)
		return nullptr;
	currentNode->height = max(currentNode->leftChild->getHeight(), currentNode->rightChild->getHeight()) + 1;
	int balanceFactor = this->getBalanceFactor(currentNode);
	if (balanceFactor > 1 && getBalanceFactor(currentNode->leftChild) > 0)
		return rightRotate(currentNode);
	if (balanceFactor < -1 && getBalanceFactor(currentNode->rightChild) < 0)
		return leftRotate(currentNode);
	if (balanceFactor > 1 && getBalanceFactor(currentNode->leftChild) < 0) {
		root->leftChild = leftRotate(currentNode->leftChild);
		return rightRotate(currentNode);
	}
	if (balanceFactor < -1 && getBalanceFactor(currentNode->leftChild) > 0) {
		root->rightChild = rightRotate(currentNode->rightChild);
		return leftRotate(currentNode);
	}
	return currentNode;
}
template <typename T>
T AVL<T>::valueofNearestLeaf() {
	Node<T>* node = valueofNearestLeaf(_root);
	return node->getValue();
}
template <typename T>
Node<T>* AVL<T>::valueofNearestLeaf(Node<T>* root) {
	if (root == nullptr)
		return NULL;
	Node<T>* currentNode = root;
	if (root->leftChild == nullptr && root->rightChild == nullptr);
	else if (root->leftChild == nullptr && root->rightChild != nullptr)
		currentNode = valueofNearestLeaf(root->rightChild);
	else if (root->leftChild != nullptr && root->rightChild == nullptr)
		currentNode = valueofNearestLeaf(root->leftChild);
	else if (root->leftChild->getHeight() < root->rightChild->getHeight()) 
		currentNode = valueofNearestLeaf(root->leftChild);
	else if (root->leftChild->getHeight() > root->rightChild->getHeight()) 
		currentNode = valueofNearestLeaf(root->rightChild);
	else {  
		currentNode = valueofNearestLeaf(root->leftChild);
		Node<T>* currentNode2 = valueofNearestLeaf(root->rightChild);
		return currentNode->getHeight() < currentNode2->getHeight() ? currentNode : currentNode2;
	}
	return currentNode;
}